;;============================================================
;;
;; Tony Hyun Kim
;; 6.001 Project 3
;; Recitation: Dr. Koile/Jim
;;
;;============================================================
(load "sudoku.scm")


;;============================================================
;;
;; Question 1: Making columns
;; Status:     No known bugs
;;
;;============================================================
(define (make-column n rows)
  ; collect the nth element of each row into a column
  ; n specifies which element to collect, starting from 0
  ; type: int,List<Row> -> Column
  (map (lambda (x) (list-ref x n)) rows))

(define test-rows (make-rows *size*))
(define test-column (make-column 0 test-rows))

; Testing to make sure that the code functions properly. In 
; particular, to see if it is sharing the internal structure
;------------------------------------------------------------
; test-column
; ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
; (set-cdr! (car test-column) '(1))
; test-rows
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
;------------------------------------------------------------
; (set-cdr! (cadddr test-column) '(2 3))
; test-rows
; (((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 2 3)     (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
;------------------------------------------------------------
; (define test-column (make-column 3 test-rows))
; (set-cdr! (caddr test-column) '(1 4))
; test-rows
; (((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
;------------------------------------------------------------
; The structure seems to be shared nicely.


;;============================================================
;;
;; Question 2: Making regions
;; Status:     No known bugs.
;;
;;============================================================
(define (make-some-regions some-rows)
  ; takes a few rows of the grid (a number of rows equal to (region-size))
  ; and returns their regions.
  ; type: List<Row> -> List<Region>
  
  ; Note: We check whether the actual entries in each ROW is empty. This is
  ; the important part. If we are passed for instance some-rows as '(() () () ()),
  ; then (null? some-rows) returns false, although there are no more elements to
  ; process. The correct behavior is obtained by checking whether an
  ; actual row has elements in it.
  (if (null? (car some-rows))
      '()
      (let ((current-region (map (lambda (x) (first-n     x (region-size))) some-rows))
            (rest-region    (map (lambda (x) (but-first-n x (region-size))) some-rows)))
        (cons (foldr append '() current-region)
              (make-some-regions rest-region))
      )
  )
)
(define test-rows    (make-rows *size*))
(define test-columns (make-columns test-rows))
(define test-regions (make-regions test-rows))
; Testing to make sure that the code functions properly. In 
; particular, to see if it is sharing the internal structure.
; (Note, the following are called in succession.)
;------------------------------------------------------------
; (set-value-row! test-rows 0 0 1) 
; test-columns
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
; test-regions
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
;------------------------------------------------------------
; (set-value-row! test-rows 2 1 4)
; test-columns
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 4)       (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
; test-regions
; ((cell 1)        (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 4)       (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4)))
;------------------------------------------------------------
; (set-value-row! test-rows 3 3 3)
; test-columns
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 4)       (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 3)))
; test-regions
; (((cell 1)       (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 4)       (cell 1 2 3 4) (cell 1 2 3 4))
;  ((cell 1 2 3 4) (cell 1 2 3 4) (cell 1 2 3 4) (cell 3)))
;------------------------------------------------------------
; All of the corresponding changes were made as expected.

;;============================================================
;;
;; Question 3: Play-with-backtrack
;; Status:     No known bugs.
;;
;;============================================================
(set! *size* 9)

; My abstraction for commands
;------------------------------------------------------------
; Constructor
(define (make-command row col val)
  (list row col val)
)
; Accessors
(define (get-row cmd) (first  cmd))
(define (get-col cmd) (second cmd))
(define (get-val cmd) (third  cmd))

; Wrapper for applying a command to a grid
;------------------------------------------------------------
(define (apply-cmd grid cmd)
  (set-value! grid (get-row cmd)
                   (get-col cmd)
                   (get-val cmd))
)

; Play-with-backtrack: implementation is as suggested in the problem.
; i.e. I maintain a list of commands ('cmd-list') with the most recent
; commands in the front. This ordering is chosen so that we can backtrack,
; i.e. remove the most recent command, by simply taking the 'cdr'
;------------------------------------------------------------
(define (play-with-backtrack initial-values)
  (let ((grid (make-grid)))
    (set-initial-values! grid initial-values)
    (display-grid grid)
    (backtrack-driver-loop grid '() initial-values)
  )
)

; Note that 'backtrack-driver-loop' requires two additional 
; parameters: 'cmd-list' to keep track of the commands, and
; 'initial-values' so that it can reset the grid when asked to
; backtrack.
;------------------------------------------------------------
(define (backtrack-driver-loop grid cmd-list initial-values)
  ; The following are mostly identical to the original
  ; 'basic-driver-loop' provided, except that my program has the decency
  ; to say "please" after its remarks.
  (define (do-quit) (void))
  (define (do-unknown input)
    (printf "~n Don't recognize character ~a. Try again please." input)
    (backtrack-driver-loop grid cmd-list initial-values)
  )
  (define (do-set)
    (newline)
    (printf "What row?")
    (let ((r (read)))
      (newline)
      (printf "What column?")
      (let ((c (read)))
        (newline)
        (printf "What value?")
        ; Note: In order to take advantage of the abstraction for commands, as 
        ; 'r' 'c' and 'v' are read in, they are immediately packaged into the
        ; abstraction, and further manipulations are done at the abstraction level.
        (let* ((v (read))
               (current-cmd (make-command r c v)))
          (apply-cmd grid current-cmd)
          (printf "~nHere is your change ~n")
          (display-grid grid)
          
          ; Problem 4: Update rows, columns and regions
          ;------------------------------------------------------------
          ;(map (lambda (x) (eliminate-row x)) (get-rows grid))
          ;(map (lambda (x) (eliminate-col x)) (get-columns grid))
          ;(map (lambda (x) (eliminate-region x)) (get-regions grid))
          
          ; Problem 5: Update rows, columns and regions smarter
          ;------------------------------------------------------------
          (eliminate grid)
                    
          (printf "~nWith automatic elimination (Problem 4/5) ~n")
          (display-grid grid)
          
          (backtrack-driver-loop grid
                                 (cons current-cmd cmd-list) ; Attach to our cmd-list
                                 initial-values)
        )
      )
    )
  )
  
  ; Problem 3: do-backtrack
  ;------------------------------------------------------------
  (define (do-backtrack)
   ; First thing: we check whether there are actually any commands to backtrack
    (if (zero? (length cmd-list))
        (begin
          (printf "~nThere are no commands to backtrack. Sorry?~n")
          ; Loop
          (backtrack-driver-loop grid cmd-list initial-values)
        )
        ; Simple backtracking:
        ;------------------------------------------------------------
        ; 1) Create a new grid,
        ; 2) Initialize the new grid,
        ; 3) Execute all but the last command
        (let ((new-grid     (make-grid))
              (new-cmd-list (cdr cmd-list))) ; Remove the most recent command
          (set-initial-values! new-grid initial-values)
          ; Comments on the 'map':
          ;------------------------------------------------------------
          ; 1) I use this technique because I find this to be a succinct 
          ;    method to apply all the pertinent commands "at once." 
          ; 2) The only case in which the 'reverse' makes a difference is 
          ;    I think when the user has set the value of the same cell to
          ;    a different number more than once. If we do not do 'reverse'
          ;    then the oldest value will be used in the reconstruction of the
          ;    grid, rather than the most recent. This is undesirable behavior.
          ; 3) 'map' is supposedly creating a new list whose elements are...?
          ;    As seen by the definition of 'apply-cmd', the procedure does not
          ;    actually return anything. I thought this would cause a problem,
          ;    and originally had 'apply-cmd' return the 'cmd' after processing. 
          ;    However, experimentation showed that that was not necessary.
          (map (lambda (x) 
                 (apply-cmd new-grid x)
                 (eliminate new-grid)  ;; Problem 5: To have the backtrack function correctly
                                       ;;            with the automatic elimination
               ) 
               (reverse new-cmd-list))
          (printf "~nHere is your change ~n")
          (display-grid new-grid)
          ; Loop with the new state
          (backtrack-driver-loop new-grid new-cmd-list initial-values)
       )
   )          
  )
   
  (printf "~nEnter a command, one of (q b s)~n")
  (let ((input (read)))
    (cond ((eq? input 'q) (do-quit))
          ((eq? input 'b) (do-backtrack))
          ((eq? input 's) (do-set))
          (else (do-unknown input))
    )
  )
)

; Test-case of 'play-with-backtrack'
; (I have condensed the input to conserve space)
;------------------------------------------------------------
; (play-with-backtrack *initial-9x9-values*)
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . . 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | . 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> s; What row? 0; What column? 0; What value? 5
; Here is your change 
; -------------------------
; | 5 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . . 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | . 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> b;
; Here is your change 
; ------------------------- (BACKTRACKED '5' AT POSITION (0,0))
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . . 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | . 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> b;
; There are no commands to backtrack. Sorry?
;
; Enter a command, one of (q b s) -> s; What row? 8; What column? 0; What value? 6
; Here is your change 
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . . 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | 6 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> s; What row? 6; What column? 7; What value? 6
; Here is your change 
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . 6 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | 6 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> s; What row? 6; What column? 7; What value? 2
; Here is your change 
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . 2 2 | 
; | . . 7 | 2 . 6 | 9 . . | 
; | 6 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> b
; Here is your change 
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . 6 2 | (BACKTRACKED THE LAST ASSIGNMENT)
; | . . 7 | 2 . 6 | 9 . . | 
; | 6 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> b
; Here is your change 
; -------------------------
; | . 6 . | 1 . 4 | . 5 . | 
; | . . 8 | 3 . 5 | 6 . . | 
; | 2 . . | . . . | . . 1 | 
; -------------------------
; | 8 . . | 4 . 7 | . . 6 | 
; | . . 6 | . . . | 3 . . | 
; | 7 . . | 9 . 1 | . . 4 | 
; -------------------------
; | 5 . . | . . . | . . 2 |  (CONSECUTIVE BACKTRACKS)
; | . . 7 | 2 . 6 | 9 . . | 
; | 6 4 . | 5 . 8 | . 7 . | 
; -------------------------
; Enter a command, one of (q b s) -> q

;;============================================================
;;
;; Question 4: Row/Column/Region elimination
;; Status:     
;;
;;============================================================

; Name: is-it-in-lst?
; Description: A helper function that takes a list and element
;              and checks whether the element occurs in the list.
; Type: List<A>,A -> boolean
; Status: No problems.
;------------------------------------------------------------
(define (is-it-in-lst? lst elem)
    (cond ((null? lst) #f)
          ((= (car lst) elem) #t)
          (else (is-it-in-lst? (cdr lst) elem))
    )
  )

; Name: unique-values-of-cells
; Type: List<Cells> -> List<numbers>
; Status: No problems. (See test cases below)
;------------------------------------------------------------
; (define test-row (make-row *size*)); (Note: *size* is 9 right now)
; (set-cell-values! (first  test-row) '(1))
; (set-cell-values! (second test-row) '(2))
; (unique-values-of-cells test-row) -> (1 2)
;------------------------------------------------------------
; (define test-row (make-row *size*))
; (set-cell-values! (first  test-row) '(3))
; (set-cell-values! (second test-row) '(3))
; (unique-values-of-cells test-row) -> (3)
;------------------------------------------------------------
; (define test-row (make-row *size*))
; (unique-values-of-cells test-row) -> ()
;------------------------------------------------------------
(define (unique-values-of-cells cell-list)
  (define (iter todo result)
    (if (null? todo)
        result
        ;; Check to see if the cell has a unique value
        (if (= 1 (length (cell-values (car todo))))
            (let ((curr-cell-val (car (cell-values (car todo)))))
              (if (is-it-in-lst? result curr-cell-val)
                  (iter (cdr todo) result) ;; We already have it in our list.
                  (iter (cdr todo) (append result (list curr-cell-val))) ;; We don't have it in our list,
                                                                         ;; so let's add it.
              )
            )
            (iter (cdr todo) result)
        )
    )
  )
  (iter cell-list '())
)

; Name: eliminate-cell
; Type: Cell,List<numbers> -> Cell
; Description: Takes a cell and a list of numbers, and removes the 
;              cell-values of entries that are contained in the list.
; Status: No known bugs (See test-cases below)
;------------------------------------------------------------
; (define my-cell (make-cell))
; (eliminate-cell my-cell '(1)) -> (cell 2 3 4 5 6 7 8 9)
;------------------------------------------------------------
; (define my-cell (make-cell))
; (eliminate-cell my-cell '()) -> (cell 1 2 3 4 5 6 7 8 9)
;------------------------------------------------------------
; (define my-cell (make-cell))
; (eliminate-cell my-cell '(6 3 8)) -> (cell 1 2 4 5 7 9)
;------------------------------------------------------------
(define (eliminate-cell cell elim-lst)
  (define (iter prev curr)
    (if (not (null? curr))
        ;; If we are not at the end of the list, check whether our
        ;; current value is contained in elim-lst
        (if (is-it-in-lst? elim-lst (car curr)) 
            ;; If it is, then we mutate the cdr of the previous pair 
            ;; to skip the current value.
            (begin 
              (set-cdr! prev (cdr curr))
              (iter     prev (cdr curr))
            )
            ;; Otherwise, just increment the 'prev' and 'curr' pointers.
            (iter curr (cdr curr))
        )
    )
  )
  (iter cell (cdr cell))
  cell
)

; Name: eliminate-cell-lst
; Type: List<Cells> -> List<Cells>
; Description: Takes a list of cells, collects the set of unique values 
;              to that list of cells, and eliminates these unique values
;              from the rest.
; Status: No known bugs (See test-cases below)
;------------------------------------------------------------
; For each of the cases below, I use:
;  (define test-row (make-row *size*))
; ((cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9))
;------------------------------------------------------------
; (set-cell-values! (first test-row) '(9))
; test-row -> 
; ((cell 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9)
;  (cell 1 2 3 4 5 6 7 8 9))
; (eliminate-cell-lst test-row) ->
; ((cell 9)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8)
;  (cell 1 2 3 4 5 6 7 8))
;------------------------------------------------------------
; (define test-row (make-row *size*))
; (set-cell-values! (list-ref test-row 0) '(9))
; (set-cell-values! (list-ref test-row 1) '(3))
; (set-cell-values! (list-ref test-row 2) '(2))
; (set-cell-values! (list-ref test-row 3) '(1))
; (set-cell-values! (list-ref test-row 4) '(7))
; (set-cell-values! (list-ref test-row 5) '(5))
; (set-cell-values! (list-ref test-row 6) '(4))
; (set-cell-values! (list-ref test-row 7) '(6)) i.e. Every value known except for the last cell
; test-row ->
; ((cell 9) (cell 3) (cell 2) (cell 1) (cell 7) (cell 5) (cell 4) (cell 6) (cell 1 2 3 4 5 6 7 8 9))
; (eliminate-cell-lst test-row)
; ((cell 9) (cell 3) (cell 2) (cell 1) (cell 7) (cell 5) (cell 4) (cell 6) (cell 8))
; Eliminate-cell-lst found the right value for us!
;------------------------------------------------------------
(define (eliminate-cell-lst cell-lst)
  (let ((elim-lst (unique-values-of-cells cell-lst)))
    (map (lambda (x)
           ;; If the cell only has one value, then we obviously
           ;; should not eliminate it
           (if (> (length (cell-values x)) 1)
               (eliminate-cell x elim-lst)
               x
           )
         ) 
         cell-lst)
  )
)

; Note that we have now solved the general case of elimination for
; the list of cells. As 'row', 'column' and 'region' are all just
; lists of cells, they can be processed in an identical fashion. However,
; just for convenience and readability, we may define the following:
;------------------------------------------------------------
(define (eliminate-row row) 
  (eliminate-cell-lst row))
(define (eliminate-col col)
  (eliminate-cell-lst col))
(define (eliminate-region region)
  (eliminate-cell-lst region))

; Elimination at work
;------------------------------------------------------------
;(play-with-backtrack *initial-9x9-values*)
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | . . . | . . 1 | 
;-------------------------
;| 8 . . | 4 . 7 | . . 6 | 
;| . . 6 | . . . | 3 . . | 
;| 7 . . | 9 . 1 | . . 4 | 
;-------------------------
;| 5 . . | . . . | . . 2 | 
;| . . 7 | 2 . 6 | 9 . . | 
;| . 4 . | 5 . 8 | . 7 . | 
;-------------------------
;Enter a command, one of (q b s) -> s; What row? 8; What column? 0; What value? 6 
;Here is your change 
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | . . . | . . 1 | 
;-------------------------
;| 8 . . | 4 . 7 | . . 6 | 
;| . . 6 | . . . | 3 . . | 
;| 7 . . | 9 . 1 | . . 4 | 
;-------------------------
;| 5 . . | . . . | . . 2 | 
;| . . 7 | 2 . 6 | 9 . . | 
;| 6 4 . | 5 . 8 | . 7 . | 
;-------------------------
;With automatic elimination (Problem 4) 
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | . . 9 | . . 1 | 
;-------------------------
;| 8 . . | 4 . 7 | . . 6 | 
;| . . 6 | 8 . 2 | 3 . . | 
;| 7 . . | 9 . 1 | . . 4 | 
;-------------------------
;| 5 . . | 7 . . | . . 2 | 
;| . . 7 | 2 . 6 | 9 . . | AUTOMATICALLY FILLED OUT SEVERAL ENTRIES!
;| 6 4 . | 5 . 8 | 1 7 3 |  
;-------------------------
;Enter a command, one of (q b s) -> s; What row? 6; What column? 7; What value? 6
;Here is your change 
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | . . 9 | . . 1 | 
;-------------------------
;| 8 . . | 4 . 7 | . . 6 | 
;| . . 6 | 8 . 2 | 3 . . | 
;| 7 . . | 9 . 1 | . . 4 | 
;-------------------------
;| 5 . . | 7 . . | . 6 2 | 
;| . . 7 | 2 . 6 | 9 . . | 
;| 6 4 . | 5 . 8 | 1 7 3 | 
;-------------------------
;With automatic elimination (Problem 4) 
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | 6 . 9 | . . 1 | 
;-------------------------
;| 8 . . | 4 3 7 | . . 6 | 
;| . . 6 | 8 5 2 | 3 . . |  HERE IS AN OBVIOUS CASE OF THE ELIMINATION PROCESS
;| 7 . . | 9 . 1 | . . 4 |  NOT WORKING WELL
;-------------------------
;| 5 . . | 7 . 3 | . 6 2 | 
;| . . 7 | 2 . 6 | 9 . . | 
;| 6 4 . | 5 9 8 | 1 7 3 | 
;-------------------------
;Enter a command, one of (q b s) -> b
;Here is your change 
;-------------------------
;| . 6 . | 1 . 4 | . 5 . | 
;| . . 8 | 3 . 5 | 6 . . | 
;| 2 . . | . . . | . . 1 | 
;-------------------------
;| 8 . . | 4 . 7 | . . 6 | 
;| . . 6 | . . . | 3 . . |  FURTHERMORE, THE ELIMINATION STEPS COMPLICATE THE 
;| 7 . . | 9 . 1 | . . 4 |  BACKTRACK STAGES. 
;-------------------------
;| 5 . . | . . . | . . 2 | 
;| . . 7 | 2 . 6 | 9 . . | 
;| 6 4 . | 5 . 8 | . 7 . | 
;-------------------------
;Enter a command, one of (q b s) -> q

;;============================================================
;;
;; Question 5: Smarter Row/Column/Region elimination
;; Status:     
;;
;;============================================================

;; We need to slightly change the 'eliminate-cell' so that we
;; can easily count the number of changes made. Now, eliminate should 
;; return 1 if a change is made. 0, if nothing.
(define (eliminate-cell cell elim-lst)
  (define (iter prev curr)
    (if (not (null? curr))
        ;; If we are not at the end of the list, check whether our
        ;; current value is contained in elim-lst
        (if (is-it-in-lst? elim-lst (car curr)) 
            ;; If it is, then we mutate the cdr of the previous pair 
            ;; to skip the current value.
            (begin
              (set!     removed-something? true)
              (set-cdr! prev (cdr curr))
              (iter     prev (cdr curr))
            )
            ;; Otherwise, just increment the 'prev' and 'curr' pointers.
            (iter curr (cdr curr))
        )
    )
  )
  (define removed-something? false)
  (iter cell (cdr cell))
  (if removed-something? 1 0)
)

;; Corresponding change in eliminate-cell-lst
(define (eliminate-cell-lst cell-lst)
  (let ((elim-lst (unique-values-of-cells cell-lst)))
    (foldr + 0 (map (lambda (x)
                      ;; If the cell only has one value, then we obviously
                      ;; should not eliminate it
                      (if (> (length (cell-values x)) 1)
                          (eliminate-cell x elim-lst)
                          0 ;; Nothing eliminated
                      )
                    )
                    cell-lst))
  )
)

;; Eliminate loop continues until the removal-count is zero.
(define (eliminate grid)
  (define (iter count)
    (if (not (zero? count))
        (let ((row-count (foldr + 0 (map (lambda (x) (eliminate-row x))    (get-rows grid)))   )
              (col-count (foldr + 0 (map (lambda (x) (eliminate-col x))    (get-columns grid))))
              (reg-count (foldr + 0 (map (lambda (x) (eliminate-region x)) (get-regions grid)))))
          (iter (+ row-count col-count reg-count))
        )
    )
  )
  (iter 1) ;; Start with a nonzero count
)